package BFS.层序遍历;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的最大宽度: https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
 */
public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }

    // bfs + 队列.  利用数组list 模拟队列
    public int widthOfBinaryTree(TreeNode root) {
        // 根据题目要求, root 不为空. value 是节点的位置下标
        // 用数组模拟队列
        List<Pair<TreeNode, Integer>> list = new ArrayList<>();

        int x = 1, ret = 0; // 假设根节点为1, 那么孩子节点就是2x 和 2x + 1
        list.add(new Pair<>(root, 1));

        // bfs 主逻辑
        while (!list.isEmpty()) {
            // 更新这一层的宽度. 队列不好找到最后一个, 所以用list 数组模拟
            int n = list.size();
            int start = list.get(0).getValue();
            int end = list.get(n - 1).getValue();
            ret = Math.max(ret, end - start + 1);

            // 让下一层入队
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for (Pair<TreeNode, Integer> pair : list) {
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if(node.left != null) {
                    tmp.add(new Pair<>(node.left, index * 2));
                }
                if(node.right != null) {
                    tmp.add(new Pair<>(node.right, index * 2 + 1));
                }
            }
            // 然后把 ret 覆盖掉. 模拟栈头出栈操作
            list = tmp;
        }
        return ret;
    }


    // bfs + 队列
    public int widthOfBinaryTree2(TreeNode root) {
        // 根据题目要求, root 不为空. value 是节点的位置下标
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        List<Pair<TreeNode, Integer>> list = new ArrayList<>();

        int x = 1; // 那么孩子节点就是2x 和 2x + 1
        queue.offer(new Pair<>(root, x));

        // bfs 主逻辑
        while (!queue.isEmpty()) {
            // 更新这一层的宽度. 队列不好找到最后一个, 所以用list 数组模拟
            int n = list.size();
            int start = list.get(0).getValue();
            int end = list.get(n - 1).getValue();

            List<Pair<TreeNode, Integer>> tmp1 = new ArrayList<>();

            // 让下一层入队
            for (int i = 0; i < n; i++) {
                // 弹出栈顶元素
                Pair<TreeNode, Integer> tmp = queue.poll();
                // 加入孩子节点
                if(tmp.getKey().left != null) queue.offer(new Pair<>(tmp.getKey().left, 2 * (tmp.getValue())));
                if(tmp.getKey().right != null) queue.offer(new Pair<>(tmp.getKey().right, 2 * (tmp.getValue()) + 1));
            }
        }
        return 0;
    }

}
